package com.data.algorithm.Queue8;

/**
 * 八皇后问题
 * 介绍：
 *     回溯算法的经典案例，在8*8格的国际象棋上摆放8个皇后，使其不能相互攻击，既：
 *  任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？
 *
 * 解析：
 *     1 第一个皇后先放第一行第一列
 *     2 第二个皇后放第二行第一列，然后判断是否OK，如果不OK,继续放第二列，第三列，依次把所有列都放完
 *     3 继续放第三个皇后，还是第一列，第二列。。。直到第8个皇后也能放在一个不冲突的位置，算是找到一个正确的答案。
 *     4 当得到一个正确答案时，再退回上个栈，开始回溯，既得到所有解。
 *     5
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/3/4
 */
public class Queue8 {

    //表示有多少皇后
    private int max = 8;

    //定义一个数组表示棋盘，下标表示行，值表示列
    private int [] array;

    //记录正确答案数量
    private static int count = 0;

    public Queue8() {
        this.array = new int[this.max];
    }

    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法", count);
    }

    /**
     * 放置第n个皇后
     * @param n
     */
    private void check(int n) {
        if (n == this.max) {
            //n=8时，说明前8个皇后已经放好（n=0是第一个），得到了正确的答案，可以打印并结束，可以返回继续回溯了
            this.print();
        } else {
            //依次放入皇后
            for(int i = 0; i < this.max; ++i) {
                this.array[n] = i;
                //如果不相互攻击，就接着放下一个
                if (this.judge(n)) {
                    //递归
                    this.check(n + 1);
                }
                //无论是发生了相互攻击，还是递归结束返回答案，都开启下一轮尝试
            }

        }
    }

    /**
     *  判断放置第n个皇后时，会不会与之前放置的皇后发生攻击
     * @param n
     * @return
     */
    private boolean judge(int n) {
        for(int i = 0; i < n; ++i) {
            //同一列，同一斜线的皇后会相互攻击
            if (this.array[i] == this.array[n] || Math.abs(n - i) == Math.abs(this.array[n] - this.array[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印棋盘中皇后所在位置，下标表示行，值表示列
     */
    private void print() {
        ++count;

        for(int i = 0; i < this.array.length; ++i) {
            System.out.print(this.array[i] + " ");
        }

        System.out.println();
    }
}
